0923. 三数之和的多种可能【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 计数 + 枚举

1. 📝 题目描述

• leetcode

给定一个整数数组 arr，以及一个整数 target 作为目标值，返回满足 i < j < k 且 arr[i] + arr[j] + arr[k] == target 的元组 i, j, k 的数量。

由于结果会非常大，请返回 10^9 + 7 的模。

---

示例 1：

输入：arr = [1,1,2,2,3,3,4,4,5,5], target = 8
输出：20
解释：
按值枚举(arr[i], arr[j], arr[k])：
(1, 2, 5) 出现 8 次；
(1, 3, 4) 出现 8 次；
(2, 2, 4) 出现 2 次；
(2, 3, 3) 出现 2 次。

示例 2：

输入：arr = [1,1,2,2,2,2], target = 5
输出：12
解释：
arr[i] = 1, arr[j] = arr[k] = 2 出现 12 次：
我们从 [1,1] 中选择一个 1，有 2 种情况，
从 [2,2,2,2] 中选出两个 2，有 6 种情况。

---

提示：

• 3 <= arr.length <= 3000
• 0 <= arr[i] <= 100
• 0 <= target <= 300

2. 🎯 s.1 - 计数 + 枚举

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {number[]} arr
 * @param {number} target
 * @return {number}
 */
var threeSumMulti = function (arr, target) {
  const MOD = 1e9 + 7
  const count = new Array(101).fill(0)
  for (const x of arr) count[x]++

  let res = 0
  for (let i = 0; i <= 100; i++) {
    for (let j = i; j <= 100; j++) {
      const k = target - i - j
      if (k < j || k > 100) continue
      if (!count[i] || !count[j] || !count[k]) continue

      if (i === j && j === k) {
        res += (count[i] * (count[i] - 1) * (count[i] - 2)) / 6
      } else if (i === j) {
        res += ((count[i] * (count[i] - 1)) / 2) * count[k]
      } else if (j === k) {
        res += (count[i] * count[j] * (count[j] - 1)) / 2
      } else {
        res += count[i] * count[j] * count[k]
      }
      res %= MOD
    }
  }

  return res
}

• 时间复杂度：$O(n+C^2)$，其中 n 是数组长度，C = 101 是值域大小
• 空间复杂度：$O(C)$，计数数组

算法思路：

• 统计每个值的出现次数 count
• 枚举所有满足 $i\le j\le k$ 且 $i+j+k=target$ 的三元组
• 根据 i、j、k 是否相等选择不同的组合公式计算方案数
• 空间复杂度：$O(1)$